МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
/
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ВИВЧЕННЯ МЕТОДІВ АНАЛІЗУ ТА СИНТЕЗУ СКІНЧЕННИХ АВТОМАТІВ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи №4
з дисципліни “Обчислювальна техніка”
для студентів базового напрямку 6.0914
“Комп’ютеризовані системи, автоматика і управління”
Затверджено
на засіданні кафедри
“Автоматика і телемеханіка”
Протокол № 10 від 22.02.2001р.
Львів - 2001
Мета роботи: вивчення методів аналізу і синтезу скінченних автоматів.
1. ОСНОВНІ ВІДОМОСТІ
Цифровий автомат - це пристрій, що здійснює прийом, зберігання і перетворення дискретної інформації за деяким алгоритмом.
Загальну теорію автоматів ділять на абстрактну і структурну. Абстрактна теорія, абстрагуючись від структури автомата (тобто не цікавлячись способом його побудови), вивчає тільки поведінку автомата відносно зовнішнього середовища.
Структурна теорія цікавиться як структурою самого автомата, так і структурою вхідних дій і реакцією на них автомата. В структурній теорії вивчаються способи побудови автоматів, способи кодування вхідних дій і реакцій на них автомата.
1.1. Абстрактні цифрові автомати. Основні поняття
Абстрактний цифровий автомат з пам’яттю А задається сукупністю п’яти об’єктів: , де , - множина абстрактних вхідних сигналів автомата А (вхідний алфавіт автомата А); , - множина абстрактних станів автомата А (алфавіт станів автомата А); , - множина абстрактних вихідних сигналів автомата А (вихідний алфавіт автомата А); - функція переходів автомата А - визначає стан автомата в такті в залежності від стану автомата і від значення вхідної букви на - ому такті:
, (1)( - дискретні моменти часу); - функція виходів автомата А - визначає значення вихідної букви на - ому такті в залежності від стану автомата і від вхідної букви на тому ж - ому такті:
(2) На множині Z як правило фіксується один із станів як початковий.
Зауваження:
Поняття стану у визначенні абстрактного автомата введено в зв’язку з тим, що більшість реальних процесів, якими керують цифрові автомати, вимагають для свого правильного протікання знання передісторії розвитку процесу в часі. Іншими словами вихідний сигнал, що видається автоматом в деякий момент часу, визначається не тільки вхідною дією на автомат (командою), але й станом, в якому автомат перебував в попередній момент часу. Наприклад, якщо потрібно побудувати автомат керування переключенням світлофору при умові, що на вхід автомата надходить тільки один абстрактний вхідний сигнал «переключити світлофор», то в кожен момент часу для організації правильної роботи автомату, крім згаданого вхідного сигналу, потрібно мати також інформацію про попередній стан світлофора.
Букви - це не є в загальному випадку двійкові (або інші цифрові) змінні. Це абстрактне значення відповідно вхідної інформації, стану автомата і вихідної інформації, які відрізняються від всіх інших можливих значень. Вже на рівні структурної теорії кожну з цих букв можна закодувати певною кількістю цифрових (наприклад двійкових) змінних. Наприклад, на рівні абстрактної теорії деяка абстрактна вхідна буква може мати значення «збільшити швидкість в 2 рази», а на рівні структурної теорії ця абстрактна буква може бути закодована двома структурними двійковими змінними і мати значення 10: (, ).
Загалом, абстрактний автомат реалізує відображення множини букв вхідного в множину букв вихідного алфавітів і має тільки один вхідний і один вихідний канали, а отже є лише математичною моделлю реального процесу.
Функція виходів автомата може бути двох типів. Якщо вихідний сигнал автомата визначається виразом (2), тобто залежить як від стану автомата, так і від вхідного сигналу, то пристрій називають автоматом Мілі. Якщо ж вихідний сигнал не залежить від вхідного, а однозначно визначається станом автомата:
, (3)то пристрій називають автоматом Мура.
Є різні способи задання функцій виходів і переходів . В цій роботі ми будемо користуватися табличним способ...